package stack.easy;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 */
@SuppressWarnings("all")
public class 用栈实现队列 {
    class MyQueue {
        // 队列：先进先出
        // 栈：先进后出

        Deque<Integer> stackPush; // 处理进栈
        Deque<Integer> stackPop; // 处理出栈


        /** Initialize your data structure here. */
        public MyQueue() {
            stackPush = new ArrayDeque<>();
            stackPop = new ArrayDeque<>();
        }

        /**
         * 对于此问题我们有两种实现方式：
         * 1. 对于push操作我们和往常一样，直接push进stackPush
         *    但是对于pop和peek操作我们都需要实现将stackPush栈中的元素放置到stackPop栈中
         *    然后记录stackPop栈顶的元素，再将stackPop栈中的元素重新放置到stackPush
         *
         * 2. 在push的时候将当前入栈元素放置到栈顶，则对于peek和pop都可以做到O(1)，显然
         * 第二种方式好得多
         */
        /** Push element x to the back of queue. */
        public void push(int x) {
            while(!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
            stackPush.push(x);
            while(!stackPop.isEmpty()) {
                stackPush.push(stackPop.pop());
            }
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            return stackPush.pop();
        }

        /** Get the front element. */
        public int peek() {
            return stackPush.peek();
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            return stackPush.isEmpty();
        }
    }
}
